#include <stdio.h>

#define MaxSize 6

//定义一个静态链表结构
typedef struct {
    //数据
    int data;
    //指针（数组中的下标值）
    int next;
} component;

//将结构体数组中所有分量链接到备用链表中
void reserveArr(component *array);

//初始化静态链表
int initArr(component *array);

//打印链表
void displayArr(component *array, int body);

//从备用链表上摘下空闲节点的函数
int mallocArr(component *array);

//增加，就是把备用链表中的节点摘除一个给新的节点，然后把新的节点指向主链表的尾端即可。
int insertArr(component *array, int firstNode, int location, int num);

//备用链表回收的空间函数，array为存储数据的数组，k表示未使用节点所在数组的下标
void freeArr(component *array, int k);

int deleteArr(component *array, int location, int num);

int findArr(component *array, int location, int num);

void updateArr(component *array, int location, int old, int new);

int main() {
    //声明一个静态链表所使用的内存,其实就是定义一个数组
    component array[MaxSize];
    int firstNode = initArr(array);
    printf("静态链表的主链表值为: \n");
    displayArr(array, firstNode);
    printf("静态链表的备链表值为: \n");
    displayArr(array, 0);
    printf("------------ \n");

    int insertData = 10;
    printf("为静态链表在第%d的位置上插入一个数据: %d \n", 2, insertData);
    firstNode = insertArr(array, firstNode, 2, insertData);
    displayArr(array, firstNode);
    printf("静态链表的备链表值为: \n");
    displayArr(array, 0);
    printf("------------ \n");
    for (int i = 0; i < MaxSize; ++i) {
        printf("index: %d data: %d,next: %d \n", i, array[i].data, array[i].next);
    }
    printf("------------ \n\n");

    int deleteData = 10;
    printf("删除链表中的一个数据: %d \n", deleteData);
    int newBody = deleteArr(array, firstNode, deleteData);
    if (newBody < 0) {
        printf("没有找到数据的位置\n");
        return -1;
    }
    displayArr(array, newBody);

    //插入数据
    insertData = 8;
    printf("为静态链表在第 %d 位置上插入一个数据: %d \n", 3, insertData);
    firstNode = insertArr(array, firstNode, 3, insertData);
    displayArr(array, firstNode);


    //查找插入数据的位置
    printf("查找数据 %d 的位置 \n", insertData);
    int location = findArr(array, firstNode, insertData);
    if (location < 0) {
        printf("没有找到数据的位置\n");
        return -1;
    }
    displayArr(array, firstNode);
    printf("数据 %d 所在的位置为 %d \n", insertData, location);
    printf("------------ \n");
    for (int i = 0; i < MaxSize; ++i) {
        printf("index: %d data: %d,next: %d \n", i, array[i].data, array[i].next);
    }
    printf("------------ \n\n");

    //把插入的数据替换为新值
    int newElem = 22;
    printf("把插入的数据 %d 替换为新值 %d \n", insertData, newElem);
    updateArr(array, firstNode, insertData, newElem);
    displayArr(array, firstNode);
    printf("------------ \n");
    for (int i = 0; i < MaxSize; ++i) {
        printf("index: %d data: %d,next: %d \n", i, array[i].data, array[i].next);
    }
    printf("------------ \n\n");

    return 0;
}

//增加，就是把备用链表中的节点摘除一个给新的节点，然后把新的节点指向主链表的尾端即可。
int insertArr(component *array, int firstNode, int location, int num) {
    //设置一个临时节点位置指向插入位置
    int tempBody = firstNode;

    //分配一个节点
    int insert = mallocArr(array);
    array[insert].data = num;

    //如果是头节点位置插入的情况
    if (location == 1) {
        array[insert].next = firstNode;
        return insert;
    }

    //找到插入位置的上一个节点
    for (int i = 1; i < location - 1; ++i) {
        tempBody = array[tempBody].next;
    }

    array[insert].next = array[tempBody].next;
    array[tempBody].next = insert;

    return firstNode;
}

//删除
int deleteArr(component *array, int location, int num) {
//通过 location 找到主链表的位置，找到值相等的那个节点的前一个节点
//把这个节点的cur指向要删除的节点的cur
//把删除的节点回收到备用链表上
    int tempBody = location;
    int del;
    int newBody;
    while (array[tempBody].data != num) {
        tempBody = array[tempBody].next;
        if (tempBody == 0) {
            printf("链表中没有找到此数据\n");
            return -1;
        }
    }

    del = tempBody;
    //如果是删除首元节点的情况,则返回新的body
    if (tempBody == location) {
        newBody = array[del].next;
        freeArr(array, del);
        return newBody;
    } else {
        tempBody = location;
        //找到该节点的上一个节点
        while (array[tempBody].next != del) {
            tempBody = array[tempBody].next;
        }
        array[tempBody].next = array[del].next;
        freeArr(array, del);
        return location;
    }
}

//查找
int findArr(component *array, int location, int num) {
//当游标值为0时，表示链表结束
    while (array[location].next != 0) {
        if (array[location].data == num) {
            return location;
        }
        location = array[location].next;
    }

    //while循环不会判断最后一个节点，补充一下判断
    if (array[location].data == num) {
        return location;
    }

    //返回-1，表示在链表中没有找到该元素
    return -1;

}

//修改
void updateArr(component *array, int location, int old, int new) {
    int elem = findArr(array, location, old);
    if (elem == -1) {
        printf("没有找到要更改的数据");
        return;
    }

    array[elem].data = new;
}

//创建备用链表
void reserveArr(component *array) {
    for (int i = 0; i < MaxSize; i++) {
        //链接节点
        array[i].next = i + 1;
    }
    //链表的最后一个节点的游标值为0
    array[MaxSize - 1].next = 0;
}

//分配可用节点
int mallocArr(component *array) {
    //获取一个未使用节点
    int i = array[0].next;
    if (array[0].next) {
        //把备用节点的首元节点指向未分配的下一个节点
        array[0].next = array[i].next;
    }
    return i;
}

//初始化静态链表
int initArr(component *array) {
    int tempBody, firstNode;
    //首先创建备用链表
    reserveArr(array);
    //分配第一个空间
    firstNode = mallocArr(array);

    //建立首元节点
    array[firstNode].data = 1;
    array[firstNode].next = 0;
    //声明一个变量，把它当指针使，指向链表的最后的一个结点，当前和首元结点重合
    tempBody = firstNode;
    //i = 2 是因为主、备链表的两个首元节点。
    for (int i = 2; i <= 4; i++) {
        //继续分配空间
        int j = mallocArr(array);
        //设置新的节点数据
        array[j].data = i;
        //把当前节点的指向为新的节点
        array[tempBody].next = j;
        //把tempBody设置为当前节点，随着i增加，逐渐向后移动
        tempBody = j;
    }
    //新链表的最后一个节点的指针设置为0
    array[tempBody].next = 0;
    return firstNode;
}

//打印链表
void displayArr(component *array, int body) {
    int tempBody = body;
    //如果传入的节点的指向不为0,则继续循环
    while (array[tempBody].next) {
        printf("%d,%d | ", array[tempBody].data, array[tempBody].next);
        tempBody = array[tempBody].next;
    }
    //因为while循环时tempBody的next不为false才会打印数据，到达最后一个时候next是false,所以需要单独打印一次
    printf("%d,%d \n", array[tempBody].data, array[tempBody].next);
}

//备用链表回收的空间函数，array为存储数据的数组，k表示未使用节点所在数组的下标
void freeArr(component *array, int k) {
    array[k].next = array[0].next;
    array[0].next = k;
}
